﻿#pragma once
#include "Index.h"
#include "ReverseList.h"

class CommonNodeBetweenList
{
public:
    /**
     * 输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空
	 * 要求：空间复杂度O(1)，时间复杂度O(n)
     */
    ListNode* findFirstCommonNode(ListNode* first_head, ListNode* second_head)
    {
        ListNode* common_node = nullptr;
        //common_node=reverseListMethod(first_head,second_head);
        //common_node = twoPtrsTraverseMethod(first_head, second_head);
        common_node = twoPtrsJoinMethod(first_head, second_head);
        return common_node;
    }
private:
    /**
     * 翻转链表法:
     *  1、遍历2个串分别求出串的长度，划分出长短链表
     *  2、短链表临时进行全部翻转
     *  3、求出从长链表表头走到翻转前的短链表表头的长度，无法走到表示没有公共节点
     *  4、短链表的翻转恢复
     *  5、根据长短链表长度、长表头到短表头长度，可以算出公共节点分别在长短链表中的长度
     */
    ListNode* reverseListMethod(ListNode* first_head, ListNode* second_head)
    {
        if (!first_head || !second_head)
            return nullptr;
        //��������ĳ���
        const int first_len = ListUtil::getListLength(first_head);
        const int second_len = ListUtil::getListLength(second_head);
        //����������ȷֳ�������Ͷ�����
        ListNode* long_head = first_len > second_len ? first_head : second_head;
        ListNode* short_head = long_head == second_head ? first_head : second_head;
        //�����������
        const int L = long_head == first_head ? first_len : second_len;
        const int S = short_head == first_head ? first_len : second_len;

        //�������������ʱ��ת�������ٷ�ת����
        ReverseList list_reverse;
        ListNode* reversed_samll_head = list_reverse.reverseListBetween(short_head, 1, S);

        //����ܴӳ�����ͷ�ߵ�������ͷ��������������ڹ����ڵ�
        const int D = ListUtil::distanceBetween(long_head, short_head);

        //���������ʱ��ת�ָ�
        list_reverse.reverseListBetween(reversed_samll_head, 1, S);

        //����ͷ�޷���ͨ�������ڹ����ڵ�
        if (D < 0)
            return nullptr;

        //�賤����ķǹ������ֳ���ΪX,������ķǹ������ֳ���ΪY���������ֵĳ���ΪZ
        //�� X+Z=L, Y+Z=S,  X+Y=D (1Ϊ�׸�����Ĺ����ڵ�)
        //ȥ��Z�� X=(L-S+D)/2 ,Y=(D-L+S)/2

        //�Ӷ�����ǰ��Y���õ������ڵ㷵��
        ListNode* common_node = ListUtil::forwardKNode(short_head, (D - L + S) / 2);
        return common_node;
    }

    /**
     * 双指针长度比较法:
     *  1、单独的遍历两个链表，得到各自的长度
     *  2、求得两链表得长度差n，其中较长的链表的指针从头先走n步
     *  3、两链表指针同步向后遍历，遇到第一个相同的节点就是第一个公共结点
     */
    ListNode* twoPtrsTraverseMethod(ListNode* first_head, ListNode* second_head)
    {
        if (!first_head || !second_head)
            return nullptr;
        //��������ĳ���
        const int first_len = ListUtil::getListLength(first_head);
        const int second_len = ListUtil::getListLength(second_head);
        //����������ȷֳ�������Ͷ�����
        ListNode* long_head = first_len > second_len ? first_head : second_head;
        ListNode* short_head = long_head == second_head ? first_head : second_head;
        //�����������
        const int L = long_head == first_head ? first_len : second_len;
        const int S = short_head == first_head ? first_len : second_len;

        ListNode* long_ptr = ListUtil::forwardKNode(long_head, L - S);
        ListNode* short_ptr = short_head;
        while (long_ptr && short_ptr)
        {
            if (long_ptr == short_ptr)
                return long_ptr;

            long_ptr = long_ptr->next;
            short_ptr = short_ptr->next;
        }
        return nullptr;
    }

    /**
     * 双指针连接法:
     *  1、判断链表情况，其中有一个为空，则不能有公共节点，返回null
     *  2、两个链表都从表头开始同步依次遍历
     *  3、不需要物理上将两个链表连在一起,仅需指针在一个链表的尾部时直接跳到另一个链表的头部.
     *  将两个链表连在一起长度都相等，对于遍历两个链表的两个指针，公共部分走的步数是一样的，非公共部分因都走了
     *  两个链表，因此也是相同的，所以绕了一圈，第一个相同的节点便是第一个公共节点
     */
    ListNode* twoPtrsJoinMethod(ListNode* first_head, ListNode* second_head)
    {
        if (!first_head || !second_head)
            return nullptr;

        ListNode* first_ptr = first_head;
        bool first_switch_list = false;

        ListNode* second_ptr = second_head;
        bool second_switch_list = false;

        while (first_ptr && second_ptr)
        {
            //�״��غϵĽڵ�Ϊ�����ڵ�
            if (first_ptr == second_ptr)
                return first_ptr;

            first_ptr = first_ptr->next;
            if (first_ptr == nullptr && !first_switch_list)
            {
                first_switch_list = true;
                first_ptr = second_head;
            }

            second_ptr = second_ptr->next;
            if (second_ptr == nullptr && !second_switch_list)
            {
                second_switch_list = true;
                second_ptr = first_head;
            }
        }
        return nullptr;
    }
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(CommonNodeBetweenListTest, findFirstCommonNode)
{
    CommonNodeBetweenList solution;
    //����������
    {
        TestingUtil::resetRandSeed();
        ListNode* head0 = ListUtil::createListFromValues(TestingUtil::randSizedInts(4000, 5000));
        EXPECT_EQ(solution.findFirstCommonNode(head0, nullptr), nullptr);
        EXPECT_EQ(solution.findFirstCommonNode(nullptr, head0), nullptr);
        EXPECT_EQ(solution.findFirstCommonNode(nullptr, nullptr), nullptr);
    }
    //û�й����ڵ�
    {
        TestingUtil::resetRandSeed();
        ListNode* head0 = ListUtil::createListFromValues(TestingUtil::randSizedInts(4000, 5000));
        ListNode* head1 = ListUtil::createListFromValues(TestingUtil::randSizedInts(4000, 5000));
        EXPECT_EQ(solution.findFirstCommonNode(head0, head1), nullptr);
    }
    //����������ڽڵ�Ϊ��һ���ڵ�(����ͬ��������)
    {
        TestingUtil::resetRandSeed();
        ListNode* head0 = ListUtil::createListFromValues(TestingUtil::randSizedInts(4000, 5000));
        EXPECT_EQ(solution.findFirstCommonNode(head0, head0), head0);
    }
    //����������ڽڵ�Ϊ���һ���Ľڵ�
    {
        TestingUtil::resetRandSeed();
        ListNode* head0 = ListUtil::createListFromValues(TestingUtil::randSizedInts(4000, 5000));
        ListNode* head1 = ListUtil::createListFromValues(TestingUtil::randSizedInts(4000, 5000));

        ListNode* tail_node = ListUtil::createListFromValues({ -1 });
        ListUtil::getListTailNode(head0)->next = tail_node;
        ListUtil::getListTailNode(head1)->next = tail_node;
        EXPECT_EQ(solution.findFirstCommonNode(head0, head1), tail_node);
    }
    //�������
    {
        TestingUtil::resetRandSeed();
        ListNode* head0 = ListUtil::createListFromValues(TestingUtil::randSizedInts(4000, 5000));
        ListNode* head1 = ListUtil::createListFromValues(TestingUtil::randSizedInts(4000, 5000));
        ListNode* head2 = ListUtil::createListFromValues(TestingUtil::randSizedInts(4000, 5000));
        ListUtil::getListNodeAt(head0, ListUtil::getListLength(head0) - 1)->next = head2;
        ListUtil::getListNodeAt(head1, ListUtil::getListLength(head1) - 1)->next = head2;
        EXPECT_EQ(solution.findFirstCommonNode(head0, head1), head2);
    }
}
#endif